/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <iostream>		// Added for cout
#include <vector>		// Added for vector

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{

	RC   rc;
	char page[PageFile::PAGE_SIZE];

	// open the index file
	if ((rc = pf.open(indexname, mode)) < 0)
	{
		if (mode == 'w')
		{
			fprintf(stderr, "Error: indexfile %s could not be opened for write.\n", indexname.c_str());
			return rc;
		}
		else
		{
			// No cout here due to instructions
			return rc;	// Not an error if index file does not exist!!!
		}
	}

	// if the end pid is zero, the file is empty.
	// The rootPid is already set to -1 by the constructor.
	// set the treeHeight to 0
	if (pf.endPid() == 0)
	{
		treeHeight = 0;			// Set treeHeight to 0 when empty so can init first node!!!
		return 0;
	}

	// Don't read page file if loading it.
	if (mode == 'w')
		return 0;


	// if the end pid is not zero, then need to read the rootPid
	// and tree height from page 0.
	// The first page is page 0 since rootpid is set to -1.	
	if ((rc = pf.read(0, page)) < 0)
	{
		// an error occurred during page read
		fprintf(stderr, "Error: indexfile %s page 0 could not be read.\n", indexname.c_str());
		pf.close();
		return rc;
	}

	// Copy the rootPid and treeHeight
	// from the page. I stored rootPid and treeheight in the first
	// 4 bytes and second 4 bytes of page 0, respectively.
	memcpy(&rootPid, page, sizeof(PageId));
	memcpy(&treeHeight, page + sizeof(PageId), sizeof(int));

	//cout << "rootPid = " << rootPid << endl;
	//cout << "treeHeight = " << treeHeight << endl;

	return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	// DO I NEED TO WRITE TO DISK HERE???
	
	
	rootPid = -1;
	treeHeight = 0;
	return pf.close();
    //return 0;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	RC rc;
	char page[PageFile::PAGE_SIZE];
	PageId  leafPid = 1;
	BTLeafNode btln;			// Stores Leaf Node
	BTLeafNode btlnSib;			// Stores Leaf Node Sibling
	int siblingKey;				// Leaf Node sibling Key
	BTNonLeafNode btnlnRoot;	// Stores Non-Leaf Node new root

	PageId cursorPid;			// Stores cursor Pid for treeHeight > 1
	PageId backCursorPid;		// Stores cursor for the back trace through the tree
	int treeLevel;				// Stores each level of treeHeight
	vector<int> traceVector;	// Stores trace through index tree

	BTNonLeafNode btnln;		// Stores Non-Leaf Node
	BTNonLeafNode btnlnSib;		// Stores Non-Leaf Node Sibling
	int midKey;					// Non-Leaf Node middle Key
    
	//cout << "key = " << key << endl;
	//cout << "endPid() = " << pf.endPid() << endl;
	//cout << "treeHeight = " << treeHeight << endl;

	// Need to initialize first node
	// writing to node initializes it and increments endPid().
	if (treeHeight == 0)
	{
		btln.insert(key, rid);
		if ((rc = btln.write(leafPid, pf)) < 0)
		{
			fprintf(stderr, "Error: leaf node %n could not be written.\n", leafPid);
			return rc;
		}

		// Write new rootPid and treeHeight to disk
		// The BtreeNode is missing this function???
		rootPid = 1;
		treeHeight = 1;
		memset(page, 0, PageFile::PAGE_SIZE);
		memcpy(&page[0], &rootPid, sizeof(int));
		memcpy(&page[sizeof(int)], &treeHeight, sizeof(int));
		if ((rc = pf.write(0, page)) < 0)
		{
			fprintf(stderr, "Error: Contents of leaf node could not be written. \n");
			return rc;
		}
		return 0;
	}

	// For treeHeight == 1, there is only a single leaf cell
	if (treeHeight == 1)
	{
		// If node is not empty, need to
		// read page from pagefile prior to inserting key.
		if ((rc = btln.read(leafPid, pf)) < 0)
		{
			fprintf(stderr, "Error: leaf node %n could not be read.\n", leafPid);
			return rc;
		}

		// if max keyCount, split node and generate new root node.
		//cout << "getKeyCount() = " << btln.getKeyCount() << endl;
		if (btln.getKeyCount() < btln.ENTRIES_PER_LEAF)
		{
			btln.insert(key, rid);
		}
		else
		{
			btln.insertAndSplit(key, rid, btlnSib, siblingKey);
			//btln.printNode();
			//btlnSib.printNode();
			// Sibling nextNode_ptr should be null
			btlnSib.setNextNodePtr(btln.getNextNodePtr());
			// Since only 1 node, endpid points to +1 or 2, so write to endpid for parent
			// nextNodePtr.
			btln.setNextNodePtr(pf.endPid());
			//cout << "btln.getNextNodePtr() = " << btln.getNextNodePtr() << endl;
			//cout << "siblingKey = " << siblingKey << endl;
			//return -1;				// Added to look at Sibling after split!!!

			// Since only 1 node, endpid points to +1 or 2, so write to endpid for new node!
			if ((rc = btlnSib.write(pf.endPid(), pf)) < 0)
			{
				fprintf(stderr, "Error: leaf node %n could not be written.\n", pf.endPid());
				return rc;
			}
			// Initialize new rootpid
			// Since endpid is +1 or now 3, I need to initialize the new root to endpid - 1 or 2.
			// When write to a new node, want to write to just endpid since this points
			// to the next available pid.
			btnlnRoot.initializeRoot(leafPid, siblingKey, (pf.endPid() - 1));
			if ((rc = btnlnRoot.write(pf.endPid(), pf)) < 0)
			{
				fprintf(stderr, "Error: leaf node %n could not be written.\n", pf.endPid());
				return rc;
			}
			// Since endpid is +1 or now 4, rootpid should be set to endpid - 1 or 3.
			rootPid = pf.endPid() - 1;
			treeHeight = 2;
			// Write new rootPid and treeHeight to disk
			// The BtreeNode is missing this function???
			memset(page, 0, PageFile::PAGE_SIZE);
			memcpy(&page[0], &rootPid, sizeof(int));
			memcpy(&page[sizeof(int)], &treeHeight, sizeof(int));
			if ((rc = pf.write(0, page)) < 0)
			{
				fprintf(stderr, "Error: Contents of leaf node could not be written. \n");
				return rc;
			}
			//cout << "endPid() = " << pf.endPid() << endl;
			//cout << "treeHeight = " << treeHeight << endl;
		}
		if ((rc = btln.write(leafPid, pf)) < 0)
		{
			fprintf(stderr, "Error: leaf node %n could not be written.\n", leafPid);
			return rc;
		}
		
		//btln.printNode();
		//btlnSib.printNode();

		return 0;
	}

	// For treeHeight > 1, there are multiple leaf cells and I have to use the locateChildPtr function
	// to find the proper leaf cell. I need to store the path from the root to the leaf cell so
	// that I can back track up the path if a split occurs. I will use a Vector<> container to store
	// the path from the root to the leaf cell.
	if (treeHeight > 1)
	{
		// Read non-leaf node/page root
		//cout << "rootPid = " << rootPid << endl;
		if ((rc = btnln.read(rootPid, pf)) < 0)
		{
			fprintf(stderr, "Error: leaf node %n could not be read.\n", rootPid);
			return rc;
		}
		treeLevel = 1;
		// Need to push the rootPid on the top of the stack!!!
		traceVector.push_back(rootPid);
		while (treeLevel < treeHeight)
		{
			// Outputs cursorPid for lower level of tree
			if ((rc = btnln.locateChildPtr(key, cursorPid)) < 0)
			{
				fprintf(stderr, "Error: locateChildPtr in non-leaf node failed.\n");
				return RC_NO_SUCH_RECORD;
			}

			// Read node/page of cursor.pid
			if ((rc = btnln.read(cursorPid, pf)) < 0)
			{
				fprintf(stderr, "Error: non-leaf node %n could not be read.\n", cursorPid);
				return rc;
			}
			//traceVector[treeLevel] = cursorPid;	// segmentation fault
			traceVector.push_back(cursorPid);
			treeLevel++;
		}

		//cout << "cursorPid = " << cursorPid << endl;

		// If node is not empty, need to
		// read page from pagefile prior to inserting key.
		if ((rc = btln.read(cursorPid, pf)) < 0)
		{
			fprintf(stderr, "Error: leaf node %n could not be read.\n", leafPid);
			return rc;
		}

		// For test
		//if (cursorPid == 3)
		//{
		//	cout << "cursorPid = " << cursorPid << endl;
		//	// print child node
		//	if ((rc = btnln.read(131, pf)) < 0)
		//	{
		//		fprintf(stderr, "Error: leaf node %n could not be read.\n", leafPid);
		//		return rc;
		//	}
		//	btnln.printNode();
		//	return -1;				// Added to look at Sibling after split!!!
		//}


		// LEAF NODE
		// if max keyCount, split node, insert sibling key into next level of tree, and
		// generate new root node if needed.
		//cout << "getKeyCount() = " << btln.getKeyCount() << endl;
		if (btln.getKeyCount() < btln.ENTRIES_PER_LEAF)
		{
			//if (rid.pid > 4091000)
			//	cout << "insert rid.pid = " << rid.pid << endl;
			btln.insert(key, rid);
			//if (key == 17701234)
			//	btln.printNode();
			//btln.printNode();

			if ((rc = btln.write(cursorPid, pf)) < 0)
			{
				fprintf(stderr, "Error: leaf node %n could not be written.\n", cursorPid);
				return rc;
			}
		}
		else
		{
			//cout << "getKeyCount() = " << btln.getKeyCount() << endl;
			//if (rid.pid > 4091000)
			//	cout << "insertAndSplit rid.pid = " << rid.pid << endl;
			btln.insertAndSplit(key, rid, btlnSib, siblingKey);
			//btln.printNode();
			//btlnSib.printNode();
			// Sibling nextNode_ptr should be null
			btlnSib.setNextNodePtr(btln.getNextNodePtr());
			// Since only 1 node, endpid points to +1 or 2, so write to endpid for parent
			// nextNodePtr.
			btln.setNextNodePtr(pf.endPid());
			//cout << "btln.getNextNodePtr() = " << btln.getNextNodePtr() << endl;
			//cout << "siblingKey = " << siblingKey << endl;
			//return -1;				// Added to look at Sibling after split!!!

			//if (siblingKey == 17701234)
			//	btlnSib.printNode();
			
			//if (pf.endPid() == 154)
			//{
			//	btlnSib.printNode();
			//	return -1;				// Added to look at Sibling after split!!!
			//}

			// Since only 1 node, endpid points to +1 or 2, so write to endpid for new node!
			if ((rc = btlnSib.write(pf.endPid(), pf)) < 0)
			{
				fprintf(stderr, "Error: leaf node %n could not be written.\n", pf.endPid());
				return rc;
			}

			if ((rc = btln.write(cursorPid, pf)) < 0)
			{
				fprintf(stderr, "Error: leaf node %n could not be written.\n", cursorPid);
				return rc;
			}

			// Recurse backup through the tree adding the sibling key until no longer splits
			treeLevel = 1;
			while (treeLevel < treeHeight)
			{
				// NON-LEAF NODE
				// insert new siblingKey one level back up the tree in the root non-leaf node.
				// For a 2 level tree, the rootpid should be node 3.
				// If node is not empty, need to
				// read page from pagefile prior to inserting key.
				backCursorPid = traceVector[treeHeight - 1 - treeLevel];
				//cout << "backCursorPid = " << backCursorPid << endl;
				if ((rc = btnln.read(backCursorPid, pf)) < 0)
				{
					fprintf(stderr, "Error: leaf node %n could not be read.\n", backCursorPid);
					return rc;
				}
				//cout << "getKeyCount() = " << btnln.getKeyCount() << endl;
				if (btnln.getKeyCount() < btnln.ENTRIES_PER_NONLEAF)
				{
					// Loads sibling key and PID into next upper level of tree
					btnln.insert(siblingKey, (pf.endPid() - 1));	
					//btnln.printNode();

					//if (siblingKey == 17701234)
					//	btnln.printNode();

					//if (siblingKey == 38321234)
					//{
					//	btnln.printNode();
					//	return -1;				// Added to look at Sibling after split!!!
					//}

					// Need to write upper level of tree here since breaking out of loop!!!
					if ((rc = btnln.write(backCursorPid, pf)) < 0)
					{
						fprintf(stderr, "Error: leaf node %n could not be written.\n", backCursorPid);
						return rc;
					}

					//if (siblingKey == 17701234)
					//{
					//	cout << "backCursorPid = " << backCursorPid << endl;
					//	return -1;				// Added to look at Sibling after split!!!
					//}

					break;					// Exit while loop when no split on treelevel!!!
				}
				// if max keyCount, split node and generate new root node.
				else
				{
					//cout << "getKeyCount() = " << btnln.getKeyCount() << endl;
					btnln.insertAndSplit(siblingKey, (pf.endPid() - 1), btnlnSib, midKey);
					//btnln.insertAndSplit(siblingKey, backCursorPid, btnlnSib, midKey);
					//cout << "siblingKey =" << siblingKey << endl;
					//cout << "midKey =" << midKey << endl;
					//btnln.printNode();
					//btnlnSib.printNode();
					//return -1;				// Added to look at Sibling after split!!!
					if ((rc = btnlnSib.write(pf.endPid(), pf)) < 0)
					{
						fprintf(stderr, "Error: leaf node %n could not be written.\n", pf.endPid());
						return rc;
					}

					// Need to write upper level of tree here since inside while loop!!!
					if ((rc = btnln.write(backCursorPid, pf)) < 0)
					{
						fprintf(stderr, "Error: leaf node %n could not be written.\n", backCursorPid);
						return rc;
					}

					// Initialize new rootpid if split is at the top of the treeHeight.
					// Since endpid is +1 or now 3, I need to initialize the new root to endpid - 1 or 2.
					// When write to a new node, want to write to just endpid since this points
					// to the next available pid.
					if (treeLevel == treeHeight -1)
					{
						//btnlnRoot.initializeRoot(backCursorPid, siblingKey, (pf.endPid() - 1));
						//cout << "Generate new Root" << endl;
						btnlnRoot.initializeRoot(backCursorPid, midKey, (pf.endPid() - 1));
						if ((rc = btnlnRoot.write(pf.endPid(), pf)) < 0)
						{
							fprintf(stderr, "Error: leaf node %n could not be written.\n", pf.endPid());
							return rc;
						}
						// Since endpid is +1 or now 4, rootpid should be set to endpid - 1 or 3.
						rootPid = pf.endPid() - 1;
						treeHeight++;
						//cout << "treeHeight = " << treeHeight << endl;
						//return -1;				// Added to look at Sibling after split!!!
						// Write new rootPid and treeHeight to disk
						// The BtreeNode is missing this function???
						memset(page, 0, PageFile::PAGE_SIZE);
						memcpy(&page[0], &rootPid, sizeof(int));
						memcpy(&page[sizeof(int)], &treeHeight, sizeof(int));
						if ((rc = pf.write(0, page)) < 0)
						{
							fprintf(stderr, "Error: Contents of leaf node could not be written. \n");
							return rc;
						}
					}
					//cout << "rootPid = " << rootPid << endl;
					//cout << "treeHeight = " << treeHeight << endl;
					//cout << "backCursorPid = " << backCursorPid << endl;
					//cout << "traceVector[0] = " << traceVector[0] << endl;
					//cout << "pf.endPid() = " << pf.endPid() << endl;

					//TEMPORARY, DELETE!!!
					//if ((rc = btln.write(cursorPid, pf)) < 0)
					//{
					//fprintf(stderr, "Error: leaf node %n could not be written.\n", cursorPid);
					//	return rc;
					//}
					//TEMPORARY, DELETE!!!
					//return -1;				// Added to look at Sibling after split!!!

				}
				treeLevel++;
			}
		}
		//if ((rc = btln.write(cursorPid, pf)) < 0)
		//{
		//	fprintf(stderr, "Error: leaf node %n could not be written.\n", cursorPid);
		//	return rc;
		//}

		//btln.printNode();
		//cout << "rootPid = " << rootPid << endl;
		//cout << "treeHeight = " << treeHeight << endl;
		//cout << "backCursorPid = " << backCursorPid << endl;
		//cout << "traceVector[0] = " << traceVector[0] << endl;
		//cout << "pf.endPid() = " << pf.endPid() << endl;

		// print child node
		//if ((rc = btln.read(1, pf)) < 0)
		//{
		//	fprintf(stderr, "Error: leaf node %n could not be read.\n", leafPid);
		//	return rc;
		//}
		//btln.printNode();

		return 0;
	}
	
	return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	RC rc;
	BTLeafNode btln;			// Stores Leaf Node
	int eid;					// Stores entry ID.
	BTNonLeafNode btnln;		// Stores Non-Leaf Node
	int treeLevel;				// Stores each level of treeHeight
	
	// When open index file, the rootpid and treeHeight
	// are loaded into the index object.
	// A tree of height one has a single node with rootPid = 1
	//cout << "treeHeight = " << treeHeight << endl;
	if (treeHeight == 1)
	{
		// Read node/page 1
		if ((rc = btln.read(rootPid, pf)) < 0)
		{
			fprintf(stderr, "Error: leaf node %n could not be read.\n", rootPid);
			return rc;
		}

		//cout << "searchKey = " << searchKey << endl;

		// NOTE: eid is the output. 
		if ((rc = btln.locate(searchKey, eid)) < 0)
		{
			fprintf(stderr, "Error: Key was not found in root leaf node.\n");
			return rc;
		}

		// output:
		cursor.pid = rootPid;
		cursor.eid = eid;
	}
	// For trees higher than 1, I need to start at the root of the tree and loop through
	// each non-leaf level of the tree using the locateChildPtr() function to find the next node/page.
	// First read the rootPid node/page and then run locateChildPtr() to find the leaf pid.
	// Then run the leaf node locate function to find the leaf eid.
	else
	{
		// Read non-leaf node/page root
		//cout << "rootPid = " << rootPid << endl;
		if ((rc = btnln.read(rootPid, pf)) < 0)
		{
			fprintf(stderr, "Error: leaf node %n could not be read.\n", rootPid);
			return rc;
		}
		treeLevel = 1;
		while (treeLevel < treeHeight)
		{
			// Outputs cursor.pid for lower level of tree
			if ((rc = btnln.locateChildPtr(searchKey, cursor.pid)) < 0)
			{
				fprintf(stderr, "Error: locateChildPtr in non-leaf node failed.\n");
				return RC_NO_SUCH_RECORD;
			}
			//cout << "cursor.pid (loop) = " << cursor.pid << endl;

			// Read node/page of cursor.pid
			if ((rc = btnln.read(cursor.pid, pf)) < 0)
			{
				fprintf(stderr, "Error: non-leaf node %n could not be read.\n", cursor.pid);
				return rc;
			}
			treeLevel++;
		}

		// Read node/page of cursor.pid
		if ((rc = btln.read(cursor.pid, pf)) < 0)
		{
			fprintf(stderr, "Error: leaf node %n could not be read.\n", cursor.pid);
			return rc;
		}

		//cout << "searchKey = " << searchKey << endl;
		//cout << "cursor.pid = " << cursor.pid << endl;

		// NOTE: eid is the output. 
		if ((rc = btln.locate(searchKey, eid)) < 0)
		{
			fprintf(stderr, "Error: Key was not found in leaf node with leaf locate function.\n");
			return rc;
		}

		// output:
		// cursor.pid &
		cursor.eid = eid;

		//cout << "cursor.pid = " << cursor.pid << endl;
		//cout << "cursor.eid = " << cursor.eid << endl;
	}

	return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	RC rc;
	BTLeafNode btln;			// Stores Leaf Node
	int nextNodePtr;			// Stores next leaf Node

	// need to read page from cursor pagefile prior to readEntry.
	if ((rc = btln.read(cursor.pid, pf)) < 0)
	{
		fprintf(stderr, "Error: leaf node could not be read.\n");
		//fprintf(stderr, "Error: leaf node %n could not be read.\n", cursor.pid);
		return rc;
	}

	//btln.printNode();
	//cout << "cursor.pid = " << cursor.pid << endl;
	//cout << "cursor.eid = " << cursor.eid << endl;

	// Get key and rid from the entry Id or eid
	if ((rc = btln.readEntry(cursor.eid, key, rid)) < 0)
	{
		fprintf(stderr, "Error: leaf node cursor eid readEntry error.\n");
		//fprintf(stderr, "Error: leaf node cursor eid %n readEntry error.\n", cursor.eid);
		return rc;
	}
	//cout << "key = " << key << endl;
	//cout << "rid.pid = " << rid.pid << endl;
	//cout << "rid.sid = " << rid.sid << endl;

	// move cursor forward
	// NOTE: a key count of 1 corresponds to an eid of 0.
	// cannot move cursor past the end of the leaf node
	// if at the end of the leaf node, move to next leaf node
	if (cursor.eid < (btln.getKeyCount() - 1))
	{
		cursor.eid++;
	}
	else
	{
		nextNodePtr = btln.getNextNodePtr();
		if (nextNodePtr == 0)
		{
			// Need to return rc<1 when end of leaf nodes to break do-while loop in SqlEngine!!!
			//cout << "in nextNodePtr if" << endl;
			//fprintf(stderr, "Error: leaf node cursor eid %n getNextNodePtr error.\n", cursor.eid);
			return RC_END_OF_TREE;
		}
		cursor.pid = nextNodePtr;
		cursor.eid = 0;
	}	

	//btln.printNode();
	//cout << "cursor.pid = " << cursor.pid << endl;
	//cout << "cursor.eid = " << cursor.eid << endl;

	return 0;
}
